package 二叉树相关问题.BST;

public class 删除二叉搜索树中的节点 {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null)
            return null;
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
            return root;
        }
        else if (root.val < key) {
            root.right = deleteNode(root.right, key);
            return root;
        }
        else {
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;
                //找到左子树中的最大值
            else {
                TreeNode max = max(root.left);
                max.left=delete(root.left);
                max.right=root.right;
                return max;
            }
        }
    }

    public TreeNode max(TreeNode root) {
        if (root.right == null)
            return root;
        return max(root.right);
    }
    //删除左子树中的最大值
    public TreeNode delete(TreeNode root){
        if (root.right==null)
            return root.left;
        root.right=delete(root.right);
        return root;
    }
}
